package other;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**题目：求帕斯卡三角形
 * y: n=5
 *           1
 *         1  1
 *        1  2  1
 *       1 3  3  1
 *      1 4  6  4  1
 * @Author Gavin
 * @date 2022.01.05 21:31
 */
public class solution_4 {
    /**
     * 解题思路：
     * 由于帕斯卡三角形的特点我们可以得出这几个关系：
     * 1. 每一行有n+1个元素
     * 2. 每一行的头尾都是1
     * 3. 每一行(i)的中间某个下标位置（j）元素的元素(i,j)的值为
     *  上一行同位置的j和j-1位置的元素的和，比如上面第五行位置的6，
     *  它的位置为（5,3）,带到公式就为（4,3）+(4,2)=6
     */
    public List<List<Integer>> solution(int n){
        List<List<Integer>> result=new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> pre=Arrays.asList(new Integer[i+1]);
            pre.set(0,1);
            pre.set(i,1);
            for (int j = 1; j <i; j++) {//中间部分元素
                pre.set(j,result.get(i-1).get(j-1)+result.get(i-1).get(j));
            }
            result.add(pre);
        }
        return result;
    }
}
